package bisection


func Exist1(arr []int, num int) bool {
	if arr == nil || len(arr) == 0 {
		return false
	}
	left, right, mid := 0, len(arr)-1, 0
	for left < right {
		mid = left + ((right - left) >> 1) // 实际就是 (left + right) / 2 的防溢出写法
		if arr[mid] == num {
			return true
		} else if arr[mid] > num {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return arr[left] == num
}

func Exist2(arr []int, num int) bool {
	if arr == nil || len(arr) == 0 {
		return false
	}
	left, right, mid := 0, len(arr)-1, 0
	for left <= right {
		mid = left + ((right - left) >> 1) // 实际就是 (left + right) / 2 的防溢出写法
		if arr[mid] == num {
			return true
		} else if arr[mid] > num {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return false
}

func BSNearRight(arr []int, num int) int {
	if arr == nil || len(arr) == 0 {
		return -1
	}
	left, right, mid, index := 0, len(arr)-1, 0, -1
	for left <= right {
		mid = left + ((right - left) >> 1)
		if arr[mid] >= num {
			index = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return index
}

func FindLocalMinIndex(arr []int) int {
	if arr == nil || len(arr) < 2 {
		return -1
	}
	if arr[0] < arr[1] {
		return 0
	}
	if arr[len(arr)-2] > arr[len(arr)-1] {
		return len(arr) - 1
	}
	left, right, mid := 0, len(arr)-1, 0
	for left < right {
		mid = left + ((right - left) >> 1)
		if arr[mid-1] > arr[mid] && arr[mid+1] > arr[mid] {
			return mid
		} else if  arr[mid-1] < arr[mid] {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return left
}